import UIKit

/*
 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

 请你将两个数相加，并以相同形式返回一个表示和的链表。

 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

 示例 1：
 输入：l1 = [2,4,3], l2 = [5,6,4]
 输出：[7,0,8]
 
 解释：342 + 465 = 807.
 
 
 
 
 示例 2：

 输入：l1 = [0], l2 = [0]
 输出：[0]
 
 
 
 
 示例 3：

 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
 输出：[8,9,9,9,0,0,0,1]
 */
public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init() { self.val = 0; self.next = nil; }
    public init(_ val: Int) { self.val = val; self.next = nil; }
    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}

func reverseListNode(head: ListNode?) -> ListNode? {
    var curr = head
    var pre: ListNode? = nil
    while (curr != nil) {
        let next = curr?.next
        curr?.next = pre
        pre = curr
        curr = next
    }
    return pre
}

func printNode(head: ListNode?) {
    var node = head
    while(node != nil) {
        print(node?.val)
        node = node?.next
    }
}

// 时间：O(n) 空间：O(1)
func twoSumAdd1(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    var l11 = l1
    var l22 = l2
    printNode(head: l11)
    printNode(head: l22)
    var tempNode: ListNode? = ListNode(-1, nil)
    var resultNode: ListNode? = tempNode
    
    var jin: Int = 0
    
    while(l11 != nil || l22 != nil || jin == 1) {
        // 求和
        let sum = (l11?.val ?? 0) + (l22?.val ?? 0) + jin
        // 当前的和值
        let result = sum % 10
        // 下一位是否要进位
        jin = sum / 10
        // 建立node
        tempNode?.next = ListNode(result, nil)
        
        tempNode = tempNode?.next
        print(result)
        l11 = l11?.next
        l22 = l22?.next
    }
    
    resultNode = resultNode?.next
    return resultNode
}


var l1 = ListNode(2, nil)
l1.next = ListNode(4, .init(9, nil))

var l2 = ListNode(5, nil)
l2.next = ListNode(6, .init(4, .init(9)))


let result = twoSumAdd1(l1, l2)
printNode(head: result)
